package com.learn.algorithm.graph;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 图的表示法
 * 1. 邻接矩阵法 n个节点 使用 n*n 的矩阵matrix进行表示
 * matrix[i][j] 表示第i个节点和第j个节点是否有连接,以及连接的权重
 * 无向图 matrix[i][j] == matrix[j][i]
 * 有向图 matrix[i][j] 可以不等于 matrix[j][i]
 * 2. 邻接表法
 * ArrayList<ArrayList<int>> 不带权 ArrayList<ArrayList<int[]>> 带权
 * n个节点的图 申请n+1个链表
 * 有向
 * 0: {}
 * 1: {3, 2} 1->3 1->2
 * 2: {4, 3} 2->4 2->4
 * 3: {1, }  3->1
 * 4: {3, }  4->3
 * 无向
 * 双向添加元素
 * <p>
 * 3. 链式前向星
 * head 数组 下标表示节点编号 值表示头边号 该数组跟点的数量有关
 * next 数组 下标表示边的编号 值表示下一条边的编号
 * to   数组 下标表示边的编号 值表示去往的点
 * cnt  表示 边的编号
 */
public class CreateGraph {
    // 定点最大数量
    public static final int MAX_VERTEX = 11;
    public static final int MAX_EDGE = 21;

    /**
     * 邻接矩阵方式
     */
    public static final int[][] graph1 = new int[MAX_VERTEX][MAX_VERTEX];

    /**
     * 邻接表方式
     */
    public static final ArrayList<ArrayList<int[]>> graph2 = new ArrayList<>();

    /**
     * 链式前向星方式
     */
    public static final int[] head = new int[MAX_EDGE];
    public static final int[] next = new int[MAX_EDGE];
    public static final int[] to = new int[MAX_EDGE];
    public static final int[] weight = new int[MAX_EDGE];
    public static int cnt;

    public static void build(int n) {
        // 初始化邻接矩阵
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                graph1[i][j] = 0;
            }
        }
        // 初始化邻接表
        graph2.clear();
        for (int i = 0; i <= n; i++) {
            graph2.add(new ArrayList<>());
        }
        // 初始化链式前向星
        cnt = 1;
        Arrays.fill(head, 1, n + 1, 0);
    }

    public static void addEdge(int from, int to, int weight) {
        // from -> to 这条边 权中是weight
        next[cnt] = head[from];
        CreateGraph.to[cnt] = to;
        CreateGraph.weight[cnt] = weight;
        head[from] = cnt++;
    }

    public static void createDirectGraph(int[][] edges) {
        // 邻接矩阵
        for (int[] edge : edges) {
            graph1[edge[0]][edge[1]] = edge[2];
        }
        // 邻接表
        for (int[] edge : edges) {
//            graph2.get(edge[0]).add(edge[1]);
            graph2.get(edge[0]).add(new int[]{edge[1], edge[2]});
            // 链式前向星
            addEdge(edge[0], edge[1], edge[2]);
        }
    }

    public static void createGraph(int[][] edges) {
        // 邻接矩阵
        for (int[] edge : edges) {
            graph1[edge[0]][edge[1]] = edge[2];
            graph1[edge[1]][edge[0]] = edge[2];
        }
        // 邻接表
        for (int[] edge : edges) {
            graph2.get(edge[0]).add(new int[]{edge[1], edge[2]});
            graph2.get(edge[1]).add(new int[]{edge[0], edge[2]});// 链式前向星
            addEdge(edge[0], edge[1], edge[2]);
            addEdge(edge[1], edge[0], edge[2]);
        }
    }

    public static void traversal(int n) {
        System.out.println("邻接矩阵遍历:");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(graph1[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("邻接表遍历:");
        for (int i = 1; i <= n; i++) {
            System.out.println(i + "(邻居、权重):");
            for (int[] edge : graph2.get(i)) {
                System.out.print("(" + edge[0] + "," + edge[1] + ") ");
            }
            System.out.println();
        }
        System.out.println("链式前向星:");
        for (int i = 1; i <= n; i++) {
            System.out.print(i + "(邻居、权重):");
            for (int ei = head[i]; ei > 0; ei = next[ei]) {
                System.out.print("(" + to[ei] + "," + weight[ei] + ") ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 理解了带权图的建立过程，也就理解了不带权图
        // 点的编号为1...n
        // 例子1自己画一下图，有向带权图，然后打印结果
        int n1 = 4;
        int[][] edges1 = {{1, 3, 6}, {4, 3, 4}, {2, 4, 2}, {1, 2, 7}, {2, 3, 5}, {3, 1, 1}};
        build(n1);
        createDirectGraph(edges1);
        traversal(n1);
        System.out.println("==============================");
        // 例子2自己画一下图，无向带权图，然后打印结果
        int n2 = 5;
        int[][] edges2 = {{3, 5, 4}, {4, 1, 1}, {3, 4, 2}, {5, 2, 4}, {2, 3, 7}, {1, 5, 5}, {4, 2, 6}};
        build(n2);
        createGraph(edges2);
        traversal(n2);
    }
}
